import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-08-18
 * Time: 10:28
 */
public class Test {
    //leetcode 1004 最大连续1的个数III
    public int longestOnes(int[] nums, int k) {
        int left = 0,right = 0,ret = 0;
        int zero = 0;
        while(right < nums.length) {
            if(nums[right] == 0) {
                zero++;
            }
            while(zero > k) {
                if(nums[left++] == 0) zero--;
            }
            ret = Math.max(ret,right-left+1);
            right++;
        }

        return ret;
    }

    //leetcode 1658 将 x 减到 0 的最小操作数
    public int minOperations(int[] nums, int x) {
        int sum = 0;
        for(int n : nums) sum += n;
        int target = sum - x;
        if(target < 0) return -1;
        int ret = -1;
        int tmp = 0;
        for(int left = 0,right = 0; right < nums.length; right++) {
            tmp += nums[right];
            while(tmp > target) {
                tmp -= nums[left++];
            }

            if(tmp == target) {
                ret = Math.max(ret,right-left+1);
            }
        }

        return ret == -1 ? -1 : nums.length-ret;
    }

    //leetcode 904 水果成篮
    public int totalFruit(int[] fruits) {
        int[] hash = new int[fruits.length];
        int ret = 0;
        for(int left = 0,right = 0,kinds = 0; right < fruits.length; right++) {
            if(hash[fruits[right]] == 0) kinds++;
            hash[fruits[right]]++;
            while(kinds > 2) {
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) kinds--;
                left++;
            }
            ret = Math.max(ret,right-left+1);
        }

        return ret;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        int count = 0;
        int m = pp.length;
        for(char tmp : pp) hash1[tmp -'a']++;
        for(int left = 0,right = 0; right < ss.length; right++) {
            int in = ss[right] - 'a';
            if(++hash2[in] <= hash1[in]) count++;
            if(right - left + 1 > m) {
                if(hash2[ss[left] - 'a']-- <= hash1[ss[left] - 'a']) count--;
                left++;
            }

            if(count == m) list.add(left);
        }

        return list;
    }

    //leetcode 30 串联所有单词的子串
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        for(String tmp : words) map.put(tmp,map.getOrDefault(tmp,0) + 1);

        int m = words.length;
        int len = (words[0]).length();
        for(int i = 0; i < len; i++) {
            Map<String,Integer> map1 = new HashMap<>();
            for(int left = i, right = i, count = 0; right <= s.length() - len; right += len) {
                String str = s.substring(right,right+len);
                map1.put(str,map1.getOrDefault(str,0) + 1);
                if(map1.get(str) <= map.getOrDefault(str,0)) count++;
                if(right - left + 1 > len * m) {
                    String str2 = s.substring(left,left + len);
                    if(map1.get(str2) <= map.getOrDefault(str2,0)) count--;
                    map1.put(str2,map1.get(str2) - 1);
                    left += len;
                }
                if(count == m) list.add(left);
            }
        }

        return list;
    }
}
